package leetcode;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0496.java
 * @Author : WangRuoyu
 * @Date 2023/11/4 21:06
 */


public class Q0496 {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] bigOnRight = new int[10010];
        Arrays.fill(bigOnRight, -1);
        ArrayList<Integer> stack = new ArrayList<>();
        stack.add(100000);
        for (int i = nums2.length - 1; i >= 0; i--) {
            while (nums2[i] >= stack.get(stack.size() - 1)) stack.remove(stack.size() - 1);
            bigOnRight[nums2[i]] = stack.get(stack.size() - 1);
            stack.add(nums2[i]);
        }
        for (int i = 0; i < nums1.length; i++) {
            int big = bigOnRight[nums1[i]];
            nums1[i] = big == 100000 ? -1 : big;
        }
        return nums1;
    }

    public static void main(String[] args) {
        Q0496 sl = new Q0496();
        int[] nums1 = {4, 1, 2};
        int[] nums2 = {1, 3, 4, 2};
        System.out.println(Arrays.toString(sl.nextGreaterElement(nums1, nums2)));
    }
}